//
// Created by win10 on 2024/12/18.
//
#include <stdio.h>
#include <stdlib.h>

// 定义二叉排序树的节点结构
typedef struct Node {
    int data;
    struct BitNode* lchild;
    struct BitNode* rchild;
} BitNode;

// 创建一个新节点
BitNode* createNode(int data) {
    BitNode* newNode = (BitNode*)malloc(sizeof(BitNode));
    if (!newNode) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    return newNode;
}

// 查找某个值
BitNode * search(BitNode * root, int key) // 1.root 树的根节点 2.key 需要查找的值
{
    if (!root){
        return NULL;
    }
    if (root->data == key){
        return root;
    }
    if (key < root->data){
        return search(root->lchild, key);
    }
    if (key > root->data){
        return search(root->rchild, key);
    }
}

// 插入某个值
BitNode * insert(BitNode * root, int key){
    if (!root){
        root = createNode(key);
    } else if (key < root->data)
    {
        root->lchild = insert(root->lchild, key);
    } else if (key > root->data)
    {
        root->rchild = insert(root->rchild, key);
    } else
    {
        printf("node has been existed");
        return root;
    }
    return root;

}

// 中序遍历（查看二叉排序树内容）
void inorderTraversal(BitNode* root) {
    if (root != NULL) {
        inorderTraversal(root->lchild);
        printf("%d ", root->data);
        inorderTraversal(root->rchild);
    }
}

int main()
{
    BitNode* NodeA = createNode(122);
    BitNode* NodeB = createNode(99);
    BitNode* NodeC = createNode(110);
    BitNode* NodeD = createNode(105);
    BitNode* NodeE = createNode(250);

    NodeA->lchild = NodeB;
    NodeA->rchild = NodeE;

    NodeB->rchild = NodeC;
    NodeC->lchild = NodeD;

    inorderTraversal(NodeA);


    BitNode * result = search(NodeA, 105);
    printf("\n%d\n", result->data);

    NodeA = insert(NodeA, 103);
    inorderTraversal(NodeA);
}